#define _CRT_SECURE_NO_WARNINGS 1
/*方法一:使用erase删除重复数据，不过会导致数据挪动，时间复杂度为O(N*N)
*思路：
* 1. 由于数据是排序好的，通过查询每一个数据的重复区间
* 2. 将重复区间进行删除，只保留一个数据即可
*/
class Solution {
public:
	int removeDuplicates(vector<int>& nums)
	{
		if (nums.size() == 1)
			return 1;
		vector<int>::iterator it = nums.begin();
		vector<int>::iterator it1 = it;
		it1++;

		while (it != nums.end())
		{
			while (it1 != nums.end() && *it1 == *it)
				it1++;
			it = nums.erase(++it, it1);
			it1 = it;
			it1++;
		}
		return nums.size();
	}
};

/*方二:时间复杂度为O(N)
*思路：
* 1. 由于数据是排序好的，通过查询每一个数据的重复区间
* 2. 将重复区间进行删除，只保留一个数据即可
*/
int removeDuplicates(int* nums, int numsSize)
{
	int src1 = 0, src2 = 1;
	int dst = 0;
	// 跟上题的思路一致，相同的数只保留一个，依次往前放
	while (src2 < numsSize)
	{
		nums[dst] = nums[src1];
		++dst;
		//如果两个指针指向的元素不重复，则指针同时向后移动
		if (nums[src1] != nums[src2])
		{
			++src1;
			++src2;
		}
		else
		{
			//如果重复，找到第一个不重复的元素
			while (src2 < numsSize && nums[src1] == nums[src2])
			{
				++src2;
			}
			//更新指针
			src1 = src2;
			++src2;
		}
	}
	if (src1 < numsSize)
	{
		nums[dst] = nums[src1];
		++dst;
	}
	return dst;
}